package com.platform.modules.alg.alglib.poj2243;

import java.util.LinkedList;
import java.util.Queue;

import static com.platform.modules.alg.alglib.poj2243.Poj2243.*;

public class Poj2243 {
    public static int maxn = 40;
    public static int K = 26; // 代表 26 个字
    public static int root; // 字典树的根
    public static int L; // 字典树节点个数
    public String output = "";
    ACAutomata ac = new ACAutomata();

    // 矩阵乘法
    public static mat mul(mat A, mat B) {
        mat C = new mat(A.n);
        for (int i = 0; i < A.n; i++)
            for (int j = 0; j < B.n; j++)
                for (int k = 0; k < A.n; k++)
                    C.a[i][j] += A.a[i][k] * B.a[k][j];
        return C;
    }

    // A^n
    public static mat pow(mat A, int n) {
        mat ans = new mat(A.n);
        for (int i = 0; i < A.n; i++)
            ans.a[i][i] = 1; // 单位矩阵
        while (n > 0) {
            if ((n & 1) > 0)
                ans = mul(ans, A);
            A = mul(A, A);
            n >>= 1;
        }
        return ans;
    }

    // 求26+26^2+...+26^n
    int pow_2(int n) {
        mat C = new mat(2);
        C.a[0][0] = 26;
        C.a[0][1] = C.a[1][1] = 1;
        C = pow(C, n);
        int ans = C.a[0][0] + C.a[0][1];
        return --ans;
    }

    public String cal(String input) {
        int n;
        String[] line = input.split("\n");
        for (int i = 0; i < line.length; ) {
            ac.init();
            String[] num = line[i++].split(" ");
            n = Integer.parseInt(num[1]);
            String[] str = line[i++].split(" ");
            for (String s : str) {
                ac.insert(s);
            }
            ac.build();
            output += (pow_2(n) - ac.query(n)) + "\n";
        }
        return output;
    }
}

class mat {
    int a[][] = new int[maxn][maxn];
    int n;

    mat(int _n) {
        n = _n;
    }
}

class ACAutomata {
    int next[][] = new int[maxn][K];
    int fail[] = new int[maxn];
    int end[] = new int[maxn];
    int id[] = new int[maxn];

    // 新建结点
    int newNode() {
        for (int i = 0; i < K; i++)
            next[L][i] = -1;
        end[L] = 0;
        return L++;
    }

    // 初始化
    void init() {
        L = 0;
        root = newNode();
    }

    // 插入一个词根
    void insert(String s) {
        int len = s.length();
        ;
        int p = root;
        for (int i = 0; i < len; i++) {
            int ch = s.charAt(i) - 'a';
            if (next[p][ch] == -1)
                next[p][ch] = newNode();
            p = next[p][ch];
        }
        end[p]++;
    }

    // 构建 AC 自动机
    void build() {
        Queue<Integer> Q = new LinkedList<>(); // 队列，BFS使用
        fail[root] = root;
        for (int i = 0; i < K; i++) {
            if (next[root][i] == -1) {
                next[root][i] = root;
            } else {
                fail[next[root][i]] = root;
                Q.add(next[root][i]);
            }
        }
        while (!Q.isEmpty()) {
            int now = Q.peek();
            Q.poll();
            if (end[fail[now]] > 0)
                end[now]++; // 重要!!如果当前结点的失败指针end有结束标记，当前结点的end++
            for (int i = 0; i < K; i++) {
                if (next[now][i] != -1) {
                    fail[next[now][i]] = next[fail[now]][i];
                    Q.add(next[now][i]);
                } else
                    next[now][i] = next[fail[now]][i];
            }
        }
    }

    int query(int n) {
        int ids = 0;
        for (int i = 0; i < id.length; i++) {
            id[i] = -1;
        }
        for (int i = 0; i < L; i++) // 对未标记的结点重新编号
            if (end[i] == 0)
                id[i] = ids++;
        mat F = new mat(ids + 1);
        for (int u = 0; u < L; u++) {
            if (end[u] > 0) continue;
            for (int j = 0; j < K; j++) {
                int v = next[u][j];
                if (end[v] == 0)
                    F.a[id[u]][id[v]]++;
            }
        }
        for (int i = 0; i < ids + 1; i++)
            F.a[i][ids] = 1;
        F = pow(F, n);
        int res = 0;
        for (int i = 0; i < L; i++)
            res += F.a[0][i];
        return --res;
    }
}
